package dp;

import java.util.Arrays;

/**
 * @author tmh
 * @date 2024/9/17 16:25
 * @description
 */
public class T300最长递增子序列 {
    public static void main(String[] args) {
        int[] array = {10, 9, 2, 5, 3, 7, 101, 18};
        lengthOfLIS(array);
    }

    //dp[i]=>表示以nums[i]结尾的最长递增子序列的长度为dp[i]
    //用两个for循环来解决，这个思路就很好
    public static int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        //用result来保存最大值
        int result = 0;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                    result=Math.max(result,dp[i]);
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[len - 1];
    }
}
